[AHOI2018初中组] 分组

type

status

date

slug

summary

题目描述

小可可的学校信息组总共有个队员，每个人都有一个实力值。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：[1, 2, 3, 4, 5] 是合法的分组方案，因为实力值连续；不是合法的分组方案，因为实力值不连续；同样不是合法的分组方案，因为出现了两个实力值为的选手。

如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行：

第一行一个正整数，表示队员数量。

第二行有个整数，第个整数表示第个队员的实力。

输出格式

输出一行，包括一个正整数，表示人数最少的组的人数最大值。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例解释】分为组，一组的队员实力值是，一组是，其中最小的组人数为，可以发现没有比更优的分法了。

【数据范围】

对于的数据满足：，。

本题共个测试点，编号为，每个测试点额外保证如下：

测试点编号	数据限制

	且互不相同
	, 互不相同

题解

对应于前两个测试点，由于没有重复元素，所以我们可以直接将数组排序，然后遍历判断。

对于后面的测试点，我们可以模仿之前的思路，同样先进行排序，与之前不同的是，我们需要考虑这些重复的元素。例如，由于是有序的，所以相同的元素不能放在前面一组内，显然应该放在应该新的组内，也就是这个会有两个分组，答案为。那么如果后面还有元素，比如，我们需要加入额外的判断。与两个测试点对比，对于前两个测试点，由于不存在相同的元素，是能放就放的原则。对于同元素的测试点，先让将放在较小的集合内更好，也就是有多个集合能放时每次放小的集合内，也就是贪心的思想。

下面是完整代码：